In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the``deepness of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.

Summary and Contributions: This is a theoretical work that gives an example of a class of (distribution,hypothesis)-pairs which: (i) can be learnt efficiently using a 1-layer neural net with random initialization and gradient descent; yet (ii) under any embedding, any linear function obtaining vanishing loss requires exponentially large weights. The construction goes roughly as follows: the hypotheses (parity on a subset A of the coordinates) is quite hard given uniform samples. The distribution has 50% weight on uniform samples, and another 50% on samples that are particularly easy for the given hypothesis (all coordinates in A have identical signs). Since the embedding cannot depend on the distribution, it has no chance of being useful on the hard part for a typical hypothesis. For the learning algorithm, the algorithm first uses the easy half to learn to assign high, positive weights to coordinates in A .

This is a very nice paper showing that gradient descent on a carefully regularized hinge loss, two layer network can learn certain sparse parity problems with sample complexity in a certain sense exponentially better than linear methods (including RKHS and NTK after converting to finite width). The reviews and discussions were all eventually in favor, and I personally really enjoyed this paper and also its proof, which I studied in some detail, and plan to investigate even more. Personally, to understand things, I chose q k 18 and n k 40, which I think is kindof implied as natural by the upper bound (it makes the bound like 1/k). While these exponents are large, I think it would help the story for many readers. You can even write "poly"... (b) I think you can spend some time/space explaining the distributional assumption, and what breaks down if you remove it.

In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the deepness" of deep networks.

In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the ``deepness" of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.